#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge
{
    int aim, weight;
};
const int MAXN = 1000;
const int INF = ~(1 << 31);
vector<edge> vertex[MAXN];
int d[MAXN];
queue<int> que;
bool SPFA(int s, int n, int v)
{ //Shortest Path Faster Algorigthm
    //bool flag;//标记从遍历当前节点出发的边是否导致目标节点的最短距离缩短，不用标记
    for (int i = 0; i < v; ++i)
    {
        que.push(i);
    }
    int size, index;
    for (int i = 0; i < n; ++i)
    {
        size = que.size();
        for (int j = 0; j < size; ++j)
        {
            index = que.front(); //取队首元素
            que.pop();
            for (int k = 0; k < vertex[index].size(); ++k)
            {
                if (d[vertex[index][k].aim] > d[index] + vertex[index][k].weight)
                { //有松弛，把目标节点，放到队列当中
                    d[vertex[index][k].aim] = d[index] + vertex[index][k].weight;
                    que.push(vertex[index][k].aim); //把松弛过的结点加入到队列中
                }
            }
        }
    }
    if (!que.empty())
    {//判断是否有负环
        for (int i = que.front(); !que.empty();)
        {
            for (int j = 0; j < vertex[i].size(); ++j)
            {
                if (d[vertex[i][j].aim] > d[i] + vertex[i][j].weight)
                {
                    return false;
                }
            }
        }
    }
    return true;
}
int main()
{
    fill(d, d + MAXN, INF);
}